package chapter01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum2 {
    /**
     *  回溯法 process(candidates, target, count,new ArrayList<>(),pos)
     *  从数组candidates下标为pos的位置开始组合数字
     *  递归条件
     *      1) 小列表中数字之加 > target || pos >= candidates.length
     *          直接返回
     *      2) 小列表中数字之加 == target
     *          将小列表加入大列表
     *          返回
     *      3) 小列表中数字之加 < target
     *          从candidates[pos~length-1]遍历数字，将数字加入小列表中
     *          加入小列表中的数字在进入下一次循环时，要将上一次加入的数字从小列表中移除
     *   细节
     *      为了方便统计，先将candidates排序 
     *      小列表中为了避免重复元素，如[2,3] [3,2]
     *      进行规定：小列表中元素非递减组织 即list[list.length-1] <= candidates[i]
     *               因为candidates中有重复数字，在遍历candidates过程中要进行去重操作
     *               [pos,length-1]中从pos+1位置开始比较
     *               如果[i]==[i-1] 跳过这次i
     */
    List<List<Integer>> intList=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        process(candidates, target, 0,new ArrayList<>(),0);
        return intList;
    }

    public void process(int[] candidates, int target,int count,List<Integer> res,int pos){
        if(count==target){
            intList.add(new ArrayList<>(res));
            return;
        }
        if(count>target||pos>=candidates.length){
            return;
        }
        int length=candidates.length;
        for(int i=pos;i<length;i++){
            while (i<length&&i>pos&&candidates[i]==candidates[i-1]){
                i++;
            }
            if(i<length&&(res.size()==0||res.get(res.size()-1)<=candidates[i])){
                res.add(candidates[i]);
                process(candidates, target, count+candidates[i],res,i+1);
                res.remove(res.size()-1);
            }
        }
    }
}
